/* Copyright (c) 2008 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */


#import "GDataXMLNode.h"

@class NSArray, NSDictionary, NSError, NSString, NSURL;
@class GDataXMLElement, GDataXMLDocument;


static const int kGDataXMLParseOptions = (XML_PARSE_NOCDATA | XML_PARSE_NOBLANKS);


// isEqual: has the fatal flaw that it doesn't deal well with the received
// being nil. We'll use this utility instead.

// Static copy of AreEqualOrBothNil from GDataObject.m, so that using 
// GDataXMLNode does not require pulling in all of GData.
static BOOL AreEqualOrBothNilPrivate(id obj1, id obj2) {
  if (obj1 == obj2) {
    return YES;
  }
  if (obj1 && obj2) {
    return [obj1 isEqual:obj2]; 
  } 
  return NO;
}


// convert NSString* to xmlChar*
//
// the "Get" part implies that ownership remains with str

static xmlChar* GDataGetXMLString(NSString *str) {
  xmlChar* result = (xmlChar *)[str UTF8String];
  return result;
}

// convert xmlChar* to NSString*
//
// returns an autoreleased NSString*

static NSString* GDataStringFromXMLString(const xmlChar *chars) {
  
#if DEBUG
  NSCAssert(chars != NULL, @"GDataXMLNode sees an unexpected empty string");
#endif
  if (chars == NULL) return nil;
  
  NSString *result = [NSString stringWithUTF8String:(const char *) chars];
  return result;
}

// Make a fake qualified name we use as local name internally in libxml
// data structures when there's no actual namespace node available to point to
// from an element or attribute node
//
// Returns an autoreleased NSString*

static NSString *GDataFakeQNameForURIAndName(NSString *theURI, NSString *name) {

  NSString *fakeQName = [NSString stringWithFormat:@"{%@}:%@", theURI, name];
  return fakeQName;
}


// libxml2 offers xmlSplitQName2, but that searches forwards. Since we may
// be searching for a whole URI shoved in as a prefix, like 
//   {http://foo}:name
// we'll search for the prefix in backwards from the end of the qualified name
//
// returns a copy of qname as the local name if there's no prefix
static xmlChar *SplitQNameReverse(const xmlChar *qname, xmlChar **prefix) {
  
  // search backwards for a colon
  int qnameLen = xmlStrlen(qname);
  for (int idx = qnameLen - 1; idx >= 0; idx--) {
    
    if (qname[idx] == ':') {
      
      // found the prefix; copy the prefix, if requested
      if (prefix != NULL) {
        if (idx > 0) {
          *prefix = xmlStrsub(qname, 0, idx); 
        } else {
          *prefix = NULL; 
        }
      }
      
      if (idx < qnameLen - 1) {
        // return a copy of the local name
        xmlChar *localName = xmlStrsub(qname, idx + 1, qnameLen - idx - 1);
        return localName;
      } else {
        return NULL; 
      }
    }
  }
  
  // no colon found, so the qualified name is the local name
  xmlChar *qnameCopy = xmlStrdup(qname);
  return qnameCopy;
}

@interface GDataXMLNode (PrivateMethods)

// consuming a node implies it will later be freed when the instance is 
// dealloc'd; borrowing it implies that ownership and disposal remain the
// job of the supplier of the node

+ (id)nodeConsumingXMLNode:(xmlNodePtr)theXMLNode;
- (id)initConsumingXMLNode:(xmlNodePtr)theXMLNode;

+ (id)nodeBorrowingXMLNode:(xmlNodePtr)theXMLNode;
- (id)initBorrowingXMLNode:(xmlNodePtr)theXMLNode;

// getters of the underlying node
- (xmlNodePtr)XMLNode;
- (xmlNodePtr)XMLNodeCopy;

// setter/getter of the dealloc flag for the underlying node
- (BOOL)shoudFreeXMLNode;
- (void)setShouldFreeXMLNode:(BOOL)flag;

@end

@interface GDataXMLElement (PrivateMethods)

+ (void)fixUpNamespacesForNode:(xmlNodePtr)nodeToFix
            graftingToTreeNode:(xmlNodePtr)graftPointNode;
@end

@implementation GDataXMLNode 

+ (void)load {
  xmlInitParser(); 
}

// Note on convenience methods for making stand-alone element and
// attribute nodes:
//
// Since we're making a node from scratch, we don't
// have any namespace info.  So the namespace prefix, if
// any, will just be slammed into the node name.
// We'll rely on the -addChild method below to remove
// the namespace prefix and replace it with a proper ns
// pointer.

+ (GDataXMLElement *)elementWithName:(NSString *)name {
  
  xmlNodePtr theNewNode = xmlNewNode(NULL, // namespace 
                                     GDataGetXMLString(name));
  if (theNewNode) {  
    // succeeded
    return [self nodeConsumingXMLNode:theNewNode];
  } 
  return nil;
}

+ (GDataXMLElement *)elementWithName:(NSString *)name stringValue:(NSString *)value {
  
  xmlNodePtr theNewNode = xmlNewNode(NULL, // namespace 
                                     GDataGetXMLString(name));
  if (theNewNode) {  
    
    xmlNodePtr textNode = xmlNewText(GDataGetXMLString(value));
    if (textNode) {
      
      xmlNodePtr temp = xmlAddChild(theNewNode, textNode);
      if (temp) {
        // succeeded
        return [self nodeConsumingXMLNode:theNewNode];
      } 
    } 
    
    // failed; free the node and any children
    xmlFreeNode(theNewNode);
  }
  return nil;
}

+ (GDataXMLElement *)elementWithName:(NSString *)name URI:(NSString *)theURI {
  
  // since we don't know a prefix yet, shove in the whole URI; we'll look for
  // a proper namespace ptr later when addChild calls fixUpNamespacesForNode
  
  NSString *fakeQName = GDataFakeQNameForURIAndName(theURI, name);

  xmlNodePtr theNewNode = xmlNewNode(NULL, // namespace 
                                     GDataGetXMLString(fakeQName));
  if (theNewNode) {  
      return [self nodeConsumingXMLNode:theNewNode];
  }
  return nil;
}

+ (id)attributeWithName:(NSString *)name stringValue:(NSString *)value {
  
  xmlChar *xmlName = GDataGetXMLString(name);
  xmlChar *xmlValue = GDataGetXMLString(value);
  
  xmlAttrPtr theNewAttr = xmlNewProp(NULL, // parent node for the attr
                                     xmlName, xmlValue);
  if (theNewAttr) {
    return [self nodeConsumingXMLNode:(xmlNodePtr) theNewAttr];
  } 
  
  return nil;
}

+ (id)attributeWithName:(NSString *)name URI:(NSString *)attributeURI stringValue:(NSString *)value {
  
  // since we don't know a prefix yet, shove in the whole URI; we'll look for
  // a proper namespace ptr later when addChild calls fixUpNamespacesForNode
  
  NSString *fakeQName = GDataFakeQNameForURIAndName(attributeURI, name);
  
  xmlChar *xmlName = GDataGetXMLString(fakeQName);
  xmlChar *xmlValue = GDataGetXMLString(value);
  
  xmlAttrPtr theNewAttr = xmlNewProp(NULL, // parent node for the attr
                                     xmlName, xmlValue);
  if (theNewAttr) {
    return [self nodeConsumingXMLNode:(xmlNodePtr) theNewAttr];
  }
  
  return nil;
}

+ (id)textWithStringValue:(NSString *)value {
  
  xmlNodePtr theNewText = xmlNewText(GDataGetXMLString(value));
  if (theNewText) {
    return [self nodeConsumingXMLNode:theNewText];
  } 
  return nil;
}

+ (id)namespaceWithName:(NSString *)name stringValue:(NSString *)value {
  
  xmlChar *href = GDataGetXMLString(value);
  xmlChar *prefix;
  
  if ([name length] > 0) {
    prefix = GDataGetXMLString(name);
  } else {
    // default namespace is represented by a nil prefix
    prefix = nil; 
  }

  xmlNsPtr theNewNs = xmlNewNs(NULL, // parent node
                               href, prefix);
  if (theNewNs) {  
    return [self nodeConsumingXMLNode:(xmlNodePtr) theNewNs];
  }
  return nil;
}

+ (id)nodeConsumingXMLNode:(xmlNodePtr)theXMLNode {
  Class theClass;
  
  if (theXMLNode->type == XML_ELEMENT_NODE) {
    theClass = [GDataXMLElement class];
  } else {
    theClass = [GDataXMLNode class];
  }
  return [[[theClass alloc] initConsumingXMLNode:theXMLNode] autorelease]; 
}

- (id)initConsumingXMLNode:(xmlNodePtr)theXMLNode {
  self = [super init];
  if (self) {
    xmlNode_ = theXMLNode;
    shouldFreeXMLNode_ = YES;
  }
  return self;
}

+ (id)nodeBorrowingXMLNode:(xmlNodePtr)theXMLNode {
  Class theClass;
  if (theXMLNode->type == XML_ELEMENT_NODE) {
    theClass = [GDataXMLElement class];
  } else {
    theClass = [GDataXMLNode class];
  }
  
  return [[[theClass alloc] initBorrowingXMLNode:theXMLNode] autorelease]; 
}

- (id)initBorrowingXMLNode:(xmlNodePtr)theXMLNode {
  self = [super init];
  if (self) {
    xmlNode_ = theXMLNode;
    shouldFreeXMLNode_ = NO;
  }
  return self;
}

- (void)releaseCachedValues {
  
  [cachedName_ release];
  cachedName_ = nil;

  [cachedChildren_ release];
  cachedChildren_ = nil;
  
  [cachedAttributes_ release];
  cachedAttributes_ = nil;
}

- (void)dealloc {

  if (xmlNode_ && shouldFreeXMLNode_) {
    xmlFreeNode(xmlNode_); 
  }
  
  [self releaseCachedValues];
  [super dealloc]; 
}

#pragma mark -

- (void)setStringValue:(NSString *)str {
  if (xmlNode_ != NULL && str != nil) {
    
    if (xmlNode_->type == XML_NAMESPACE_DECL) {
      
      // for a namespace node, the value is the namespace URI
      xmlNsPtr nsNode = (xmlNsPtr)xmlNode_;
      
      if (nsNode->href != NULL) xmlFree((char *)nsNode->href);
      
      nsNode->href = xmlStrdup(GDataGetXMLString(str));
      
    } else {  
      
      // attribute or element node
      
      // do we need to call xmlEncodeSpecialChars?
      xmlNodeSetContent(xmlNode_, GDataGetXMLString(str));
    }    
  }
}

- (NSString *)stringValue {
    
  NSString *str = nil;
  
  if (xmlNode_ != NULL) {
    
    if (xmlNode_->type == XML_NAMESPACE_DECL) {
      
      // for a namespace node, the value is the namespace URI
      xmlNsPtr nsNode = (xmlNsPtr)xmlNode_;
      
      str = GDataStringFromXMLString(nsNode->href);
      
    } else {  
      
      // attribute or element node
      xmlChar* chars = xmlNodeGetContent(xmlNode_);
      if (chars) {
        
        str = GDataStringFromXMLString(chars);
        
        xmlFree(chars);
      }
    }    
  }
  return str;
}

- (NSString *)XMLString {
  
  NSString *str = nil;
  
  if (xmlNode_ != NULL) {
    
    xmlBufferPtr buff = xmlBufferCreate();
    if (buff) {
      
      xmlDocPtr doc = NULL;
      int level = 0;
      int format = 0;
      
      int result = xmlNodeDump(buff, doc, xmlNode_, level, format);
      
      if (result > -1) {
        str = [[[NSString alloc] initWithBytes:(xmlBufferContent(buff))
                                        length:(xmlBufferLength(buff))
                                      encoding:NSUTF8StringEncoding] autorelease];
      }
      xmlBufferFree(buff); 
    }
  }
  
  // remove leading and trailing whitespace
  NSCharacterSet *ws = [NSCharacterSet whitespaceAndNewlineCharacterSet];
  NSString *trimmed = [str stringByTrimmingCharactersInSet:ws];
  return trimmed;
}

- (NSString *)localName {
  NSString *str = nil;
  
  if (xmlNode_ != NULL) {
    
    str = GDataStringFromXMLString(xmlNode_->name);

    // if this is part of a detached subtree, str may have a prefix in it
    str = [[self class] localNameForName:str];
  }
  return str;
}

- (NSString *)prefix {
  
  NSString *str = nil;
  
  if (xmlNode_ != NULL) {
    
    // the default namespace's prefix is an empty string, though libxml
    // represents it as NULL for ns->prefix
    str = @""; 
    
    if (xmlNode_->ns != NULL && xmlNode_->ns->prefix != NULL) {
      str = GDataStringFromXMLString(xmlNode_->ns->prefix);
    } 
  }
  return str;
}

- (NSString *)URI {
  
  NSString *str = nil;
  
  if (xmlNode_ != NULL) {
    
    if (xmlNode_->ns != NULL && xmlNode_->ns->href != NULL) {
      str = GDataStringFromXMLString(xmlNode_->ns->href);
    }
  }
  return str;
}

+ (NSString *)qualifiedNameForXMLNode:(xmlNodePtr)node {
  // internal utility
  
  NSString *str = nil;
  
  if (node != NULL) {
    if (node->type == XML_NAMESPACE_DECL) {
      
      // name of a namespace node
      xmlNsPtr nsNode = (xmlNsPtr)node;
      
      // null is the default namespace; one is the loneliest number
      if (nsNode->prefix == NULL) {
        str = @"";
      }
      else {
        str = GDataStringFromXMLString(nsNode->prefix);
      }
      
    } else if (node->ns != NULL && node->ns->prefix != NULL) {
      
      // name of a non-namespace node
      
      // has a prefix
      str = [NSString stringWithFormat:@"%s:%s", 
                                   (const char *)node->ns->prefix, node->name];
    } else {
      // lacks a prefix
      str = GDataStringFromXMLString(node->name);
    }
  }
  
  return str;
}

- (NSString *)name {

  if (cachedName_ != nil) {
    return cachedName_; 
  }
  
  NSString *str = [[self class] qualifiedNameForXMLNode:xmlNode_];
  
  cachedName_ = [str retain];

  return str;
}

+ (NSString *)localNameForName:(NSString *)name {
  if (name != nil) {
    
    NSRange range = [name rangeOfString:@":"];
    if (range.location != NSNotFound) {
      
      // found a colon
      if (range.location + 1 < [name length]) {
        NSString *localName = [name substringFromIndex:(range.location + 1)];
        return localName;
      }
    }
  }
  return name;
}

+ (NSString *)prefixForName:(NSString *)name {
  if (name != nil) {
    
    NSRange range = [name rangeOfString:@":"];
    if (range.location != NSNotFound) {
      
      NSString *prefix = [name substringToIndex:(range.location)];
      return prefix;
    }
  }
  return nil;
}

- (NSUInteger)childCount {
    
  if (cachedChildren_ != nil) {
    return [cachedChildren_ count];
  }
  
  if (xmlNode_ != NULL) {
    
    unsigned int count = 0;
    
    xmlNodePtr currChild = xmlNode_->children;
    
    while (currChild != NULL) {
      ++count;
      currChild = currChild->next;
    }
    return count;
  }
  return 0;
}

- (NSArray *)children {
  
  if (cachedChildren_ != nil) {
    return cachedChildren_; 
  }

  if (xmlNode_ != NULL) {

    NSMutableArray *array = [NSMutableArray array];
    
    xmlNodePtr currChild = xmlNode_->children;
    
    while (currChild != NULL) {
      GDataXMLNode *node = [GDataXMLNode nodeBorrowingXMLNode:currChild]; 
      [array addObject:node];
      
      currChild = currChild->next;
    }
    
    cachedChildren_ = [array retain];
    
    return array;
  }
  return nil;
}

- (GDataXMLNode *)childAtIndex:(unsigned)index {
  
  NSArray *children = [self children];
  
  if ([children count] > index) {
    
    return [children objectAtIndex:index];
  }
  return nil;
}

- (GDataXMLNodeKind)kind {
  if (xmlNode_ != NULL) {
    xmlElementType nodeType = xmlNode_->type;
    switch (nodeType) {
      case XML_ELEMENT_NODE:         return GDataXMLElementKind;
      case XML_ATTRIBUTE_NODE:       return GDataXMLAttributeKind;
      case XML_TEXT_NODE:            return GDataXMLTextKind;
      case XML_CDATA_SECTION_NODE:   return GDataXMLTextKind;
      case XML_ENTITY_REF_NODE:      return GDataXMLEntityDeclarationKind;
      case XML_ENTITY_NODE:          return GDataXMLEntityDeclarationKind;
      case XML_PI_NODE:              return GDataXMLProcessingInstructionKind;
      case XML_COMMENT_NODE:         return GDataXMLCommentKind;
      case XML_DOCUMENT_NODE:        return GDataXMLDocumentKind;
      case XML_DOCUMENT_TYPE_NODE:   return GDataXMLDocumentKind;
      case XML_DOCUMENT_FRAG_NODE:   return GDataXMLDocumentKind;
      case XML_NOTATION_NODE:        return GDataXMLNotationDeclarationKind;
      case XML_HTML_DOCUMENT_NODE:   return GDataXMLDocumentKind;
      case XML_DTD_NODE:             return GDataXMLDTDKind;
      case XML_ELEMENT_DECL:         return GDataXMLElementDeclarationKind;
      case XML_ATTRIBUTE_DECL:       return GDataXMLAttributeDeclarationKind;
      case XML_ENTITY_DECL:          return GDataXMLEntityDeclarationKind;
      case XML_NAMESPACE_DECL:       return GDataXMLNamespaceKind;
      case XML_XINCLUDE_START:       return GDataXMLProcessingInstructionKind;
      case XML_XINCLUDE_END:         return GDataXMLProcessingInstructionKind;
      case XML_DOCB_DOCUMENT_NODE:   return GDataXMLDocumentKind;
    }        
  }
  return GDataXMLInvalidKind;  
}

- (NSArray *)nodesForXPath:(NSString *)xpath error:(NSError **)error {

  NSMutableArray *array = nil;
  
  // xmlXPathNewContext requires a doc for its context, but if our elements
  // are created from GDataXMLElement's initWithXMLString there may not be
  // a document. (We may later decide that we want to stuff the doc used
  // there into a GDataXMLDocument and retain it, but we don't do that now.)
  //
  // We'll temporarily make a document to use for the xpath context.

  xmlDocPtr tempDoc = NULL;
  xmlNodePtr topParent = NULL;
  
  if (xmlNode_->doc == NULL) {
    tempDoc = xmlNewDoc(NULL);
    if (tempDoc) {
      // find the topmost node of the current tree to make the root of
      // our temporary document
      topParent = xmlNode_;
      while (topParent->parent != NULL) {
        topParent = topParent->parent;
      }
      xmlDocSetRootElement(tempDoc, topParent);
    }
  }
  
  if (xmlNode_ != NULL && xmlNode_->doc != NULL) {
    
    xmlXPathContextPtr xpathCtx = xmlXPathNewContext(xmlNode_->doc); 
    if (xpathCtx) {
      
      // anchor at our current node
      xpathCtx->node = xmlNode_;
      
      xmlXPathObjectPtr xpathObj;
      xpathObj = xmlXPathEval(GDataGetXMLString(xpath), xpathCtx);
      if (xpathObj) {
        
        // we have some result from the search
        array = [NSMutableArray array];
        
        xmlNodeSetPtr nodeSet = xpathObj->nodesetval;
        if (nodeSet) {
          
          // add each node in the result set to our array
          for (int index = 0; index < nodeSet->nodeNr; index++) {
            
            xmlNodePtr currNode = nodeSet->nodeTab[index];
            
            GDataXMLNode *node = [GDataXMLNode nodeBorrowingXMLNode:currNode]; 
            if (node) {
              [array addObject:node];
            }
          }
        }
        xmlXPathFreeObject(xpathObj);
      }
      xmlXPathFreeContext(xpathCtx);
    }
    
    if (array == nil) {
      
      // provide an error  
      //
      // TODO(grobbins) obtain better xpath and libxml errors
      const char *msg = xpathCtx->lastError.str1;
      NSDictionary *userInfo = nil;
      if (msg) {
        userInfo = [NSDictionary dictionaryWithObject:[NSString stringWithUTF8String:msg] 
                                               forKey:@"error"];
      }
      *error = [NSError errorWithDomain:@"com.google.GDataXML"
                                   code:xpathCtx->lastError.code
                               userInfo:userInfo];
    }
  }
  
  if (tempDoc != NULL) {
    xmlUnlinkNode(topParent);
    xmlSetTreeDoc(topParent, NULL);
    xmlFreeDoc(tempDoc);
  }
  return array;
}

- (NSString *)description {
  int nodeType = (xmlNode_ ? (int)xmlNode_->type : -1);
  
  return [NSString stringWithFormat:@"%@ 0x%lX: {type:%d name:%@ xml:\"%@\"}",
          [self class], self, nodeType, [self name], [self XMLString]];
}

- (id)copyWithZone:(NSZone *)zone {
  
  xmlNodePtr nodeCopy = [self XMLNodeCopy];
  
  if (nodeCopy != NULL) {
    return [[GDataXMLNode alloc] initConsumingXMLNode:nodeCopy];
  }
  return nil;
}

- (BOOL)isEqual:(GDataXMLNode *)other {
  if (self == other) return YES;
  if (![other isKindOfClass:[GDataXMLNode class]]) return NO;
  
  return [self XMLNode] == [other XMLNode]
  || ([self kind] == [other kind]
      && AreEqualOrBothNilPrivate([self name], [other name])
      && [[self children] count] == [[other children] count]);
   
}  

- (NSUInteger)hash {
  return (NSUInteger) [GDataXMLNode class];
}

- (NSMethodSignature *)methodSignatureForSelector:(SEL)selector
{
  return [super methodSignatureForSelector:selector];
}

#pragma mark -

- (xmlNodePtr)XMLNodeCopy {
  if (xmlNode_ != NULL) {
    
    // Note: libxml will create a new copy of namespace nodes (xmlNs records)
    // and attach them to this copy in order to keep namespaces within this
    // node subtree copy value.
    
    xmlNodePtr nodeCopy = xmlCopyNode(xmlNode_, 1); // 1 = recursive
    return nodeCopy;
  }
  return NULL;
}

- (xmlNodePtr)XMLNode {
  return xmlNode_;
}

- (BOOL)shoudFreeXMLNode {
  return shouldFreeXMLNode_; 
}

- (void)setShouldFreeXMLNode:(BOOL)flag {
  shouldFreeXMLNode_ = flag;
}

@end



@implementation GDataXMLElement 

- (id)initWithXMLString:(NSString *)str error:(NSError **)error {
  self = [super init];
  if (self) {    
    
    const char *utf8Str = [str UTF8String];
    // NOTE: We are assuming a string length that fits into an int.
    // int.
    xmlDocPtr doc = xmlReadMemory(utf8Str, (int)strlen(utf8Str), NULL, // URL
                                  NULL, // encoding
                                  kGDataXMLParseOptions);
    if (doc == NULL) {
      if (error) {
        // TODO(grobbins) use xmlSetGenericErrorFunc to capture error
      }
    } else {
      // copy the root node from the doc
      xmlNodePtr root = xmlDocGetRootElement(doc);
      if (root) {
        xmlNode_ = xmlCopyNode(root, 1); // 1: recursive
      }
      xmlFreeDoc(doc);
    }
    
    
    if (xmlNode_ == NULL) {
      // failure
      if (error) {
        *error = [NSError errorWithDomain:@"com.google.GDataXML"
                                     code:-1 
                                 userInfo:nil];
      }
      [self release];
      return nil; 
    }
  }
  return self;  
}

- (NSArray *)namespaces {
  
  if (xmlNode_ != NULL && xmlNode_->nsDef != NULL) {
    
    NSMutableArray *array = [NSMutableArray array];
    
    xmlNsPtr currNS = xmlNode_->nsDef;
    while (currNS != NULL) {
      
      // add this prefix/URI to the list, unless it's the implicit xml prefix
      if (!xmlStrEqual(currNS->prefix, (const xmlChar *) "xml")) {
        GDataXMLNode *node = [GDataXMLNode nodeBorrowingXMLNode:(xmlNodePtr) currNS]; 
        [array addObject:node];
      }
      
      currNS = currNS->next;
    }
    
    return array;
  }
  return nil;
}

- (void)addNamespace:(GDataXMLNode *)aNamespace {
  
  if (xmlNode_ != NULL) {
    
    [self releaseCachedValues];
    
    xmlNsPtr ns = (xmlNsPtr) [aNamespace XMLNode];
    if (ns) {
      (void)xmlNewNs(xmlNode_, ns->href, ns->prefix);
      
      // we may need to fix this node's own name; the graft point is where
      // the namespace search starts, so that points to this node too
      [[self class] fixUpNamespacesForNode:xmlNode_
                        graftingToTreeNode:xmlNode_];
    }
  }
}

- (void)addChild:(GDataXMLNode *)child {
  
  if ([child kind] == GDataXMLAttributeKind) {
    [self addAttribute:child];
    return;
  }
  
  if (xmlNode_ != NULL) {

    [self releaseCachedValues];
    
    xmlNodePtr childNodeCopy = [child XMLNodeCopy];
    if (childNodeCopy) {
      
      xmlNodePtr resultNode = xmlAddChild(xmlNode_, childNodeCopy);
      if (resultNode == NULL) {
        
        // failed to add
        xmlFreeNode(childNodeCopy); 
        
      } else {
        // added this child subtree successfully; see if it has
        // previously-unresolved namespace prefixes that can now be fixed up
        [[self class] fixUpNamespacesForNode:childNodeCopy 
                          graftingToTreeNode:xmlNode_];
      }
    }
  }
}

- (NSArray *)elementsForName:(NSString *)name {
  
  NSString *desiredName = name;
  
  if (xmlNode_ != NULL) {
        
    NSString *prefix = [[self class] prefixForName:desiredName];
    if (prefix) {
      
      xmlChar* desiredPrefix = GDataGetXMLString(prefix);
      
      xmlNsPtr foundNS = xmlSearchNs(xmlNode_->doc, xmlNode_, desiredPrefix);
      if (foundNS) {
        
        // we found a namespace; fall back on elementsForLocalName:URI:
        // to get the elements
        NSString *desiredURI = GDataStringFromXMLString(foundNS->href);
        NSString *localName = [[self class] localNameForName:desiredName];
        
        NSArray *array = [self elementsForLocalName:localName URI:desiredURI];
        return array;
      }
    } 
    
    // no namespace found for the node's prefix; try an exact match
    // for the name argument, including any prefix
    NSMutableArray *array = [NSMutableArray array];
    
    xmlNodePtr currNode = xmlNode_->children;
    
    while (currNode != NULL) {
      
      // find all children which are elements with the desired name
      if (currNode->type == XML_ELEMENT_NODE) {
        
        NSString *qName = [[self class] qualifiedNameForXMLNode:currNode];
        if ([qName isEqual:name]) {
        
          GDataXMLNode *node = [GDataXMLNode nodeBorrowingXMLNode:currNode]; 
          [array addObject:node];
        }
      }
      currNode = currNode->next;
    }
    return array;
  }
  return nil;
}

- (NSArray *)elementsForLocalName:(NSString *)localName URI:(NSString *)URI {
  
  if (xmlNode_ != NULL && xmlNode_->children != NULL) {

    NSMutableArray *array = [NSMutableArray array];

    xmlNodePtr currChild = xmlNode_->children;

    xmlChar* desiredNSHref = GDataGetXMLString(URI);
    xmlChar* desiredLocalName = GDataGetXMLString(localName);

    xmlNsPtr foundNS = xmlSearchNsByHref(xmlNode_->doc, xmlNode_, desiredNSHref);
    if (foundNS == NULL) {
      NSString *fakeQName = GDataFakeQNameForURIAndName(URI, localName);
      desiredLocalName = GDataGetXMLString(fakeQName);
    }

    while (currChild != NULL) {

      // find all children which are elements with the desired name and
      // namespace, or with the prefixed name and a null namespace
      if (currChild->type == XML_ELEMENT_NODE) {

        if (currChild->ns == foundNS
            && currChild->name != NULL
            && xmlStrEqual(currChild->name, desiredLocalName)) {

          GDataXMLNode *node = [GDataXMLNode nodeBorrowingXMLNode:currChild];
          [array addObject:node];
        }
      }
      currChild = currChild->next;
    }
    
    // we return nil, not an empty array, according to docs
    if ([array count] > 0) {
      return array;
    }
  }
  return nil;
}

- (NSArray *)attributes {
  
  if (cachedAttributes_ != nil) {
    return cachedAttributes_; 
  }
    
  if (xmlNode_ != NULL && xmlNode_->properties != NULL) {
    
    NSMutableArray *array = [NSMutableArray array];
    
    xmlAttrPtr prop = xmlNode_->properties;
    while (prop != NULL) {
      
      GDataXMLNode *node = [GDataXMLNode nodeBorrowingXMLNode:(xmlNodePtr) prop]; 
      [array addObject:node];
      
      prop = prop->next;
    }
    
    cachedAttributes_ = [array retain];
    
    return array;
  }
  return nil;
}

- (void)addAttribute:(GDataXMLNode *)attribute {
  
  if (xmlNode_ != NULL) {
    
    [self releaseCachedValues];
    
    xmlAttrPtr attrPtr = (xmlAttrPtr) [attribute XMLNode];
    if (attrPtr) {
      
      // ignore this if an attribute with the name is already present,
      // similar to NSXMLNode's addAttribute
      xmlAttrPtr oldAttr;
      
      if (attrPtr->ns == NULL) {
        oldAttr = xmlHasProp(xmlNode_, attrPtr->name);
      } else {
        oldAttr = xmlHasNsProp(xmlNode_, attrPtr->name, attrPtr->ns->href);
      }
      
      if (oldAttr == NULL) {
        
        xmlNsPtr newPropNS = NULL;

        // if this attribute has a namespace, search for a matching namespace
        // on the node we're adding to
        if (attrPtr->ns != NULL) {
          
          newPropNS = xmlSearchNsByHref(xmlNode_->doc, xmlNode_, attrPtr->ns->href);
          if (newPropNS == NULL) {
            // make a new namespace on the parent node, and use that for the
            // new attribute
            newPropNS = xmlNewNs(xmlNode_, attrPtr->ns->href, attrPtr->ns->prefix);
          }
        }
        
        // copy the attribute onto this node
        xmlChar *value = xmlNodeGetContent((xmlNodePtr) attrPtr);
        xmlAttrPtr newProp = xmlNewNsProp(xmlNode_, newPropNS, attrPtr->name, value);
        if (newProp != NULL) {
          // we made the property, so clean up the property's namespace
          
          [[self class] fixUpNamespacesForNode:(xmlNodePtr)newProp
                            graftingToTreeNode:xmlNode_];
        }
        
        if (value != NULL) {
          xmlFree(value);
        }
      }
    }
  }
}

- (GDataXMLNode *)attributeForName:(NSString *)name {
  
  if (xmlNode_ != NULL) {
    
    xmlAttrPtr attr = xmlHasProp(xmlNode_, GDataGetXMLString(name));
    if (attr == NULL) {
      
      // can we guarantee that xmlAttrPtrs always have the ns ptr and never
      // a namespace as part of the actual attribute name?
      
      // split the name and its prefix, if any
      xmlNsPtr ns = NULL;
      NSString *prefix = [[self class] prefixForName:name];
      if (prefix) {
        
        // find the namespace for this prefix, and search on its URI to find
        // the xmlNsPtr
        name = [[self class] localNameForName:name];
        ns = xmlSearchNs(xmlNode_->doc, xmlNode_, GDataGetXMLString(prefix)); 
      }
      
      const xmlChar* nsURI = ((ns != NULL) ? ns->href : NULL);
      attr = xmlHasNsProp(xmlNode_, GDataGetXMLString(name), nsURI);
    }
    
    if (attr) {
      return [GDataXMLNode nodeBorrowingXMLNode:(xmlNodePtr) attr];
    }
  }
  return nil;
}

- (GDataXMLNode *)attributeForLocalName:(NSString *)localName
                                    URI:(NSString *)attributeURI {
  
  if (xmlNode_ != NULL) {
    
    const xmlChar* name = GDataGetXMLString(localName);
    const xmlChar* nsURI = GDataGetXMLString(attributeURI);
    
    xmlAttrPtr attr = xmlHasNsProp(xmlNode_, name, nsURI);

    if (attr == NULL) {
      // if the attribute is in a tree lacking the proper namespace,
      // the local name may include the full URI as a prefix
      NSString *fakeQName = GDataFakeQNameForURIAndName(attributeURI, localName);
      const xmlChar* xmlFakeQName = GDataGetXMLString(fakeQName);

      attr = xmlHasProp(xmlNode_, xmlFakeQName);
    }

    if (attr) {
      return [GDataXMLNode nodeBorrowingXMLNode:(xmlNodePtr) attr];
    }
  }
  return nil;
}

- (NSString *)resolvePrefixForNamespaceURI:(NSString *)namespaceURI {
  
  if (xmlNode_ != NULL) {
    
    xmlChar* desiredNSHref = GDataGetXMLString(namespaceURI);
    
    xmlNsPtr foundNS = xmlSearchNsByHref(xmlNode_->doc, xmlNode_, desiredNSHref);
    if (foundNS) {
      
      // we found the namespace
      if (foundNS->prefix != NULL) {
        NSString *prefix = GDataStringFromXMLString(foundNS->prefix);
        return prefix;
      } else {
        // empty prefix is default namespace
        return @"";
      }
    }
  } 
  return nil;
}

#pragma mark Namespace fixup routines

+ (void)deleteNamespacePtr:(xmlNsPtr)namespaceToDelete
               fromXMLNode:(xmlNodePtr)node {
  
  // utilty routine to remove a namespace pointer from an element's
  // namespace definition list.  This is just removing the nsPtr
  // from the singly-linked list, the node's namespace definitions.
  xmlNsPtr currNS = node->nsDef;
  xmlNsPtr prevNS = NULL;
  
  while (currNS != NULL) {
    xmlNsPtr nextNS = currNS->next;  
    
    if (namespaceToDelete == currNS) {
      
      // found it; delete it from the head of the node's ns definition list
      // or from the next field of the previous namespace
      
      if (prevNS != NULL) prevNS->next = nextNS;
      else node->nsDef = nextNS;
      
      xmlFreeNs(currNS);
      return;
    }
    prevNS = currNS;
    currNS = nextNS;
  }
}

+ (void)fixQualifiedNamesForNode:(xmlNodePtr)nodeToFix
              graftingToTreeNode:(xmlNodePtr)graftPointNode {
  
  // Replace prefix-in-name with proper namespace pointers
  //
  // This is an inner routine for fixUpNamespacesForNode:
  //
  // see if this node's name lacks a namespace and is qualified, and if so, 
  // see if we can resolve the prefix against the parent
  //
  // The prefix may either be normal, "gd:foo", or a URI
  // "{http://blah.com/}:foo"
  
  if (nodeToFix->ns == NULL) {
    xmlNsPtr foundNS = NULL;
    
    xmlChar* prefix = NULL;
    xmlChar* localName = SplitQNameReverse(nodeToFix->name, &prefix);
    if (localName != NULL) {
      if (prefix != NULL) {
        
        // if the prefix is wrapped by { and } then it's a URI
        int prefixLen = xmlStrlen(prefix);
        if (prefixLen > 2
            && prefix[0] == '{' 
            && prefix[prefixLen - 1] == '}') {
          
          // search for the namespace by URI
          xmlChar* uri = xmlStrsub(prefix, 1, prefixLen - 2);
          
          if (uri != NULL) {
            foundNS = xmlSearchNsByHref(graftPointNode->doc, graftPointNode, uri);
            
            xmlFree(uri);
          }
        }
      }
      
      if (foundNS == NULL) {
        // search for the namespace by prefix, even if the prefix is nil
        // (nil prefix means to search for the default namespace)
        foundNS = xmlSearchNs(graftPointNode->doc, graftPointNode, prefix); 
      }
      
      if (foundNS != NULL) {
        // we found a namespace, so fix the ns pointer and the local name
        xmlSetNs(nodeToFix, foundNS);
        xmlNodeSetName(nodeToFix, localName);
      }
      
      if (prefix != NULL) {
        xmlFree(prefix);
        prefix = NULL;
      }
      
      xmlFree(localName);
    }
  }
}

+ (void)fixDuplicateNamespacesForNode:(xmlNodePtr)nodeToFix
                   graftingToTreeNode:(xmlNodePtr)graftPointNode 
             namespaceSubstitutionMap:(NSMutableDictionary *)nsMap {
  
  // Duplicate namespace removal
  //
  // This is an inner routine for fixUpNamespacesForNode:
  //
  // If any of this node's namespaces are already defined at the graft point 
  // level, add that namespace to the map of namespace substitutions 
  // so it will be replaced in the children below the nodeToFix, and
  // delete the namespace record
  
  if (nodeToFix->type == XML_ELEMENT_NODE) {
    
    // step through the namespaces defined on this node
    xmlNsPtr definedNS = nodeToFix->nsDef;
    while (definedNS != NULL) {
      
      // see if this namespace is already defined higher in the tree,
      // with both the same URI and the same prefix; if so, add a mapping for
      // it
      xmlNsPtr foundNS = xmlSearchNsByHref(graftPointNode->doc, graftPointNode, 
                                           definedNS->href);
      if (foundNS != NULL
          && foundNS != definedNS
          && xmlStrEqual(definedNS->prefix, foundNS->prefix)) {
        
        // store a mapping from this defined nsPtr to the one found higher
        // in the tree
        [nsMap setObject:[NSValue valueWithPointer:foundNS]
                  forKey:[NSValue valueWithPointer:definedNS]];
        
        // remove this namespace from the ns definition list of this node;
        // all child elements and attributes referencing this namespace
        // now have a dangling pointer and must be updated (that is done later
        // in this method)
        //
        // before we delete this namespace, move our pointer to the
        // next one
        xmlNsPtr nsToDelete = definedNS;
        definedNS = definedNS->next;

        [self deleteNamespacePtr:nsToDelete fromXMLNode:nodeToFix];
        
      } else {
        // this namespace wasn't a duplicate; move to the next
        definedNS = definedNS->next;
      }
    }
  }
  
  // if this node's namespace is one we deleted, update it to point
  // to someplace better
  if (nodeToFix->ns != NULL) {
    
    NSValue *currNS = [NSValue valueWithPointer:nodeToFix->ns];
    NSValue *replacementNS = [nsMap objectForKey:currNS];
    
    if (replacementNS != nil) {
      xmlNsPtr replaceNSPtr = [replacementNS pointerValue];
      
      xmlSetNs(nodeToFix, replaceNSPtr); 
    }
  }  
}



+ (void)fixUpNamespacesForNode:(xmlNodePtr)nodeToFix
            graftingToTreeNode:(xmlNodePtr)graftPointNode
      namespaceSubstitutionMap:(NSMutableDictionary *)nsMap {
  
  // This is the inner routine for fixUpNamespacesForNode:graftingToTreeNode:
  //
  // This routine fixes two issues:
  //
  // Because we can create nodes with qualified names before adding
  // them to the tree that declares the namespace for the prefix,
  // we need to set the node namespaces after adding them to the tree.
  //
  // Because libxml adds namespaces to nodes when it copies them,
  // we want to remove redundant namespaces after adding them to
  // a tree.
  //
  // If only the Mac's libxml had xmlDOMWrapReconcileNamespaces, it could do 
  // namespace cleanup for us

  // We only care about fixing names of elements and attributes
  if (nodeToFix->type != XML_ELEMENT_NODE
      && nodeToFix->type != XML_ATTRIBUTE_NODE) return;
  
  // Do the fixes
  [self fixQualifiedNamesForNode:nodeToFix
              graftingToTreeNode:graftPointNode];
  
  [self fixDuplicateNamespacesForNode:nodeToFix
                   graftingToTreeNode:graftPointNode
             namespaceSubstitutionMap:nsMap];
  
  if (nodeToFix->type == XML_ELEMENT_NODE) {
    
    // when fixing element nodes, recurse for each child element and 
    // for each attribute
    xmlNodePtr currChild = nodeToFix->children;
    while (currChild != NULL) {
      [self fixUpNamespacesForNode:currChild 
                graftingToTreeNode:graftPointNode
          namespaceSubstitutionMap:nsMap];
      currChild = currChild->next;
    }
    
    xmlAttrPtr currProp = nodeToFix->properties;
    while (currProp != NULL) {
      [self fixUpNamespacesForNode:(xmlNodePtr)currProp 
                graftingToTreeNode:graftPointNode
          namespaceSubstitutionMap:nsMap];
      currProp = currProp->next;
    }
  }
}

+ (void)fixUpNamespacesForNode:(xmlNodePtr)nodeToFix
            graftingToTreeNode:(xmlNodePtr)graftPointNode {
  
  // allocate the namespace map that will be passed
  // down on recursive calls
  NSMutableDictionary *nsMap = [NSMutableDictionary dictionary];
  
  [self fixUpNamespacesForNode:nodeToFix
            graftingToTreeNode:graftPointNode
      namespaceSubstitutionMap:nsMap];
}

@end



@implementation GDataXMLDocument 

- (id)initWithXMLString:(NSString *)str options:(unsigned int)mask error:(NSError **)error {
  
  NSData *data = [str dataUsingEncoding:NSUTF8StringEncoding];
  GDataXMLDocument *doc = [self initWithData:data options:mask error:error];
  return doc;
}

- (id)initWithData:(NSData *)data options:(unsigned int)mask error:(NSError **)error {
  
  self = [super init];
  if (self) {   
    
    const char *baseURL = NULL;
    const char *encoding = NULL;
    
    // NOTE: We are assuming [data length] fits into an int.
    xmlDoc_ = xmlReadMemory([data bytes], (int)[data length], baseURL, encoding,
                            kGDataXMLParseOptions); // TODO(grobbins) map option values
    if (xmlDoc_ == NULL) {
      if (error) {
       *error = [NSError errorWithDomain:@"com.google.GDataXML"
                                    code:-1 
                                userInfo:nil];
        // TODO(grobbins) use xmlSetGenericErrorFunc to capture error
        [self release];
      }
      return nil;
    }
  }
  
  return self;
}

- (id)initWithRootElement:(GDataXMLElement *)element {
  
  self = [super init];
  if (self) {    
    
    xmlDoc_ = xmlNewDoc(NULL);
    
    (void) xmlDocSetRootElement(xmlDoc_, [element XMLNodeCopy]);
  }

  return self;
}

- (NSString *)description {
  return [NSString stringWithFormat:@"%@ 0x%lX", [self class], self];
}

- (void)dealloc {
  if (xmlDoc_ != NULL) {
    xmlFreeDoc(xmlDoc_);
  }
  [super dealloc];
}

#pragma mark -

- (GDataXMLElement *)rootElement {
  GDataXMLElement *element = nil;
  
  if (xmlDoc_ != NULL) {
    xmlNodePtr rootNode = xmlDocGetRootElement(xmlDoc_); 
    if (rootNode) {
      element = [GDataXMLElement nodeBorrowingXMLNode:rootNode];
    }
  }
  return element;
}

- (NSData *)XMLData {
  
  if (xmlDoc_ != NULL) {
    xmlChar *buffer = NULL;
    int bufferSize = 0;
    
    xmlDocDumpMemory(xmlDoc_, &buffer, &bufferSize);
    
    if (buffer) {
      NSData *data = [NSData dataWithBytes:buffer
                                    length:bufferSize];
      xmlFree(buffer);
      return data;
    }
  }
  return nil;
}

- (void)setVersion:(NSString *)version {
  
  if (xmlDoc_ != NULL) {
    if (xmlDoc_->version != NULL) {
      // version is a const char* so we must cast
      xmlFree((char *) xmlDoc_->version);
      xmlDoc_->version = NULL;
    }
    
    if (version != nil) {
      xmlDoc_->version = xmlStrdup(GDataGetXMLString(version));
    }
  }
}

- (void)setCharacterEncoding:(NSString *)encoding {
  
  if (xmlDoc_ != NULL) {
    if (xmlDoc_->encoding != NULL) {
      // version is a const char* so we must cast
      xmlFree((char *) xmlDoc_->encoding);
      xmlDoc_->encoding = NULL;
    }
    
    if (encoding != nil) {
      xmlDoc_->encoding = xmlStrdup(GDataGetXMLString(encoding));
    }
  }
}

@end
